//题目 015：格子路径
//        在一个 2×2 的栅格中，从左上角出来，只能向右或向下移动，总共有 6 条路径可以到达栅
//        格的右下角：
//        求在一个 20×20 的栅格中，有多少条移动路径？
//        答案：137846528820


import java.math.BigInteger;

//    注意答案类型的选择
public class Week015 {

    //method1:  组合数
    // 总共要走m+n步，选出m向下走
    //或总共要走m+n步，选出n步向右走
    //组合数C(m+n,n)=C(m+n,m)

    //递推公式求组合数
    //n个中选m个：C(n,m)=C(n-1,m-1)+C(n-1,m);
    //规定C(n,0)=C(n,n)=1;
    //特别的，当x<y时，C(x,y)不存在
//    static void run() {
//        int n = 20, m = 20;
//        int all = n + m;
//        long[][] Combinations = new long[all + 1][all + 1];
//        for (int i = 0; i <= all; ++i) {
//            Combinations[i][0] = Combinations[i][i] = 1;
//            for (int j = 1; j <= i; ++j) {
//                Combinations[i][j] = Combinations[i - 1][j - 1] + Combinations[i - 1][j];
//            }
//        }
//        System.out.println(Combinations[n + m][m]);
//    }

    //阶乘求组合数
    //n中选m个：C(n,m)=n!/m!/(n-m)!
//    static void run() {
//        int m = 20, n = 20;
//        BigInteger ans = BigInteger.ONE;
//        for (int i = 2; i <= m + n; ++i) ans = ans.multiply(BigInteger.valueOf(i));
//        for (int i = 2; i <= m; ++i) ans = ans.divide(BigInteger.valueOf(i));
//        for (int i = 2; i <= n; ++i) ans = ans.divide(BigInteger.valueOf(i));
//        System.out.println(ans);
//    }



    //method2:  dp
    //因为 只能向右或向下移动
    //所以 到达(i,j)这个点的路径条数由(i-1,j)和(i,j-1)得出
    //dp[i][j]=dp[i-1][j]+dp[i][j-1],其中,当i或j等于0时dp[i][j]=1;
//    static void run() {
//        int m = 20, n = 20;
//        long[][] dp = new long[m + 1][n + 1];
//        for (int i = 0; i <= m; ++i) dp[i][0] = 1;
//        for (int i = 0; i <= n; ++i) dp[0][i] = 1;
//        for (int i = 1; i <= m; ++i) {
//            for (int j = 1; j <= n; ++j) {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//        System.out.println(dp[m][n]);
//    }

    //method2:  滚动数组优化dp空间复杂度
    //对于method2的dp条件，我们发现每次的结果只跟dp[i-1][j]与dp[i][j-1]有关
    //而其他的空间是用不到的，即仅与前一行有关
    //所以我们可以将第一维度的m降至2
    static void run() {
        int m = 20, n = 20;
        long[][] dp = new long[2][n + 1];
        //第一行初始化
        for (int i = 0; i <= n; ++i) dp[0][i] = 1;
        //第一列初始化
        dp[1][0] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                //x&1等于x%2
                dp[i & 1][j] = dp[(i - 1) & 1][j] + dp[i & 1][j - 1];
            }
        }
        System.out.println(dp[m & 1][n]);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
